package TreePackage;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class BinaryTree3 {

  public static void main(String[] args) {
    node node1 = new node(1);
    node node2 = new node(2);

    node node4 = new node(4);
    node node5 = new node(5);
    node node6 = new node(6);

    BinaryTree3 tree = new BinaryTree3();
    tree.root = node5;
    tree.root.setLeft(node4);
    tree.root.setRight(node6);
    node4.setLeft(node2);
    node4.setRight(node1);


    /*List<node> result = preList(tree.root);
    System.out.println(result);*/
    /*List<node> result = lastList(tree.root);
    System.out.println(result);*/
    List<node> result = middleList(tree.root);
    System.out.println(result);
  }


  private node root;

  public BinaryTree3() {
  }

  public BinaryTree3(node root) {
    this.root = root;
  }

  /**
   * 获取
   * @return root
   */
  public node getRoot() {
    return root;
  }

  /**
   * 设置
   * @param root
   */
  public void setRoot(node root) {
    this.root = root;
  }

  public String toString() {
    return "BinaryTree3{root = " + root + "}";
  }
  /*
  *  功能 : 完成二叉树的迭代前序遍历
  *  参数 : 二叉树的根节点
  * */
  public static List<node> preList(node root){
    /*定义结果集*/
    List<node> result = new ArrayList<>();

    /*判断传入的根节点是否为空*/
    if (root == null){
      return result;
    }

    /*定义一个栈, 用栈来实现迭代*/
    Stack<node> stack = new Stack<>();

    /*先将root入栈*/
    stack.push(root);

    /*循环, 当栈不为空时*/
    while(!stack.isEmpty()){

      /*将栈中treeNode弹出*/
      node node = stack.pop();

      /*将弹出的treeNode加入到result中*/
      result.add(node);


      /*
      *
      *  因为是将弹出的treeNode加入到result集合中, 所以先压入栈的treeNode后被加入到result集合中
      *  故前序遍历先将右子节点压入栈中, 后将左子节点压入栈中
      * */
      /*处理右子节点*/
      if (node.right != null){
        stack.push(node.right);
      }

      if (node.left != null){
        stack.push(node.left);
      }
    }
    /*返回结果集*/
    return result;
  }

  /*
  *  功能 : 实现二叉树的后序遍历
  *  参数 : 要实现后序遍历的树的根节点
  *  后序遍历的顺序为 左右中
  *  翻转之前的result顺序为 中右左
  *  出栈顺序为中右左, 入栈顺序为 中左右
  *
  * */
  public static List<node> lastList(node root){
    List<node> result = new ArrayList<>();
    if (root == null){
      return result;
    }
    Stack<node> stack = new Stack<>();
    stack.push(root); // 中入栈
    while(!stack.isEmpty()){
      node node = stack.pop();
      result.add(node);

      if (node.left != null){
        stack.push(node.left);
      }
      if (node.right != null){
        stack.push(node.right);
      }
    }
    Collections.reverse(result);
    return result;
  }

  /*
  *
  *  功能 : 实现二叉树的中序遍历
  *  参数 : 二叉树的根节点
  *
  * */
  public static List<node> middleList(node root){
    List<node> result = new ArrayList<>();
    Stack<node> stack = new Stack<>();
    if (root == null){
      return result;
    }

    /*定义辅助node*/
    node temp = root;

    /*当temp == null 且 stack为空时, 停止循环*/
    while(temp != null || !stack.isEmpty()){
      if (temp != null){
        stack.push(temp);
        temp = temp.left;
      }
      /*若左子节点为空, 则转向将右子节点压入栈中*/
      else{
        temp = stack.pop();
        result.add(temp);
        temp = temp.right;
      }
    }

    return result;
  }



}
class node{
  public int val;
  public node right;
  public node left;

  public node() {
  }

  public node(int val) {
    this.val = val;
  }

  /**
   * 获取
   * @return val
   */
  public int getVal() {
    return val;
  }

  /**
   * 设置
   * @param val
   */
  public void setVal(int val) {
    this.val = val;
  }

  /**
   * 获取
   * @return right
   */
  public node getRight() {
    return right;
  }

  /**
   * 设置
   * @param right
   */
  public void setRight(node right) {
    this.right = right;
  }

  /**
   * 获取
   * @return left
   */
  public node getLeft() {
    return left;
  }

  /**
   * 设置
   * @param left
   */
  public void setLeft(node left) {
    this.left = left;
  }

  public String toString() {
    return "node{val = " + val + "}";
  }
}
